/*
 * @lc app=leetcode.cn id=474 lang=typescript
 *
 * [474] 一和零
 */

// @lc code=start
function findMaxForm(strs: string[], m: number, n: number): number {
  // dp[i][j] i个0和j个1凑出最多的子集
  const dp = new Array(m + 1).fill(0).map((_) => new Array(n + 1).fill(0));

  for (let str of strs) {
    let count0 = 0;
    let count1 = 0;
    // 当前字符串0和1个个数
    for (let x of str) {
      if (x === '1') {
        count1++;
      } else {
        count0++;
      }
    }
    for (let i = m; i >= count0; i--) {
      for (let j = n; j >= count1; j--) {
        dp[i][j] = Math.max(dp[i][j], dp[i - count0][j - count1] + 1);
      }
    }
  }

  return dp[m][n];
}
// @lc code=end
